﻿using System.Collections.Generic;
using System;
using System.Diagnostics;

namespace Calc
{

    //一个极简的算数表达式计算器，支持函数，变量
	// + - * / ^
	// $

	enum OpType{
		Add, //+
		Sub, //-
		Mul, //*
		Div, ///
		Exp, //^
		Lbr, //(
		Rbr, //)
		Com, //,
		Num, //number
		Var, //variable
		Fun, //Function
		Equ, //=
	}

	enum Func{
		Max,
		Min,
		Floor,
		Cell,
		Inc,
		Dec,
		Abs,
		Round,
	}


	class Token{

		private static int IDX = 10000;

		public Token(){
			Index = ++IDX;
		}

		public bool Ignore{ set; get; }

		public int Index{ get; protected set;}

		public OpType Op{get;set;}

		public string Value{get;set;}

		public virtual double ValueOf(Dictionary<string, object> variables){
			if (Op == OpType.Num)
				return double.Parse (Value.Trim ());
			else if (Op == OpType.Var) {
				string fullValue = new string (Value.ToCharArray ());
				int ps = fullValue.IndexOf ('.');
				if (ps > 0) {
					object obj = variables[fullValue.Substring (0, ps).Trim ()];
					fullValue = fullValue.Substring (ps + 1);
					while ((ps = fullValue.IndexOf ('.')) > 0) {
						obj = obj.GetType ().GetProperty (fullValue.Substring (0, ps).Trim ()).GetValue (obj);
						fullValue = fullValue.Substring (ps + 1);
					}
					return double.Parse (obj.GetType ().GetProperty (fullValue.Trim ()).GetValue (obj).ToString ());
				} else {
					return double.Parse (variables [Value.Trim ()].ToString ());
				}
			} else {
				throw new InvalidCastException ("token " + this + " cann't has valueof method");
			}
		}

		public override string ToString ()
		{
			return string.Format ("[Token: Index={0}, Op={1}, Value={2}]", Index, Op, Value);
		}

	}

	class Expr : Token
	{

		public Expr ()
		{

		}

		public Expr (Token token)
		{
			this.Index = token.Index;
			this.Op = token.Op;
			this.Value = token.Value;
		}

		public List<Expr> Operands{ get; set; }

		public Expr AppendOperands(params Expr[] exprs){
			if (Operands == null) {
				Operands = new List<Expr> ();
			}
			Operands.AddRange (exprs);
			return this;
		}

		public Expr InsertOperands(params Expr[] exprs){
			if (Operands == null) {
				Operands = new List<Expr> ();
			}
			Operands.InsertRange(0, exprs);
			return this;
		}

		public override double ValueOf (Dictionary<string, object> variables)
		{
			double result = 0;
			switch (Op) {
			case OpType.Add:
				result = Operands [0].ValueOf (variables) + Operands [1].ValueOf (variables);
				break;
			case OpType.Sub:
				result = Operands [0].ValueOf (variables) - Operands [1].ValueOf (variables);
				break;
			case OpType.Mul:
				result = Operands [0].ValueOf (variables) * Operands [1].ValueOf (variables);
				break;
			case OpType.Div:
				result = Operands [0].ValueOf (variables) / Operands [1].ValueOf (variables);
				break;
			case OpType.Exp:
				result = Math.Pow (Operands [0].ValueOf (variables), Operands [1].ValueOf (variables));
				break;
			case OpType.Fun:
				switch((Func)Enum.Parse (typeof(Func), Value.Trim (), true)){
				case Func.Max:
					result = Operands [0].ValueOf (variables);
					for (int i = 1; i < Operands.Count; ++i)
						result = Math.Max (result, Operands [i].ValueOf (variables));
					break;

				case Func.Min:
					result = Operands [0].ValueOf (variables);
					for (int i = 1; i < Operands.Count; ++i)
						result = Math.Min (result, Operands [i].ValueOf (variables));
					break;
				case Func.Cell:
					Debug.Assert (Operands.Count == 1);
					result = Math.Ceiling (Operands [0].ValueOf (variables));
					break;
				case Func.Floor:
					Debug.Assert (Operands.Count == 1);
					result = Math.Floor(Operands [0].ValueOf (variables));
					break;
				case Func.Inc:
					Debug.Assert (Operands.Count == 1);
					result = Operands [0].ValueOf (variables) + 1;
					break;
				case Func.Dec:
					Debug.Assert (Operands.Count == 1);
					result = Operands [0].ValueOf (variables) - 1;
					break;
				case Func.Abs:
					Debug.Assert (Operands.Count == 1);
					result = Math.Abs(Operands[0].ValueOf(variables));
					break;
				case Func.Round:
					Debug.Assert (Operands.Count == 1);
					result = Math.Round(Operands[0].ValueOf(variables));
					break;
				}
				break;
			default:
				return base.ValueOf (variables);
			}
			return result;
		}
	}

	enum MachineStatus{ 
		Start, Error, Num, Name 
	}

	public class Calculator
	{
		private  static HashSet<char> EndChar = new HashSet<char> (); 
		private  static HashSet<char> NumChar = new HashSet<char> ();
		private  static HashSet<char> NameChar = new HashSet<char> ();
		private static Dictionary<char, OpType> OpTypeMap = new Dictionary<char, OpType>();

		static Calculator(){
			foreach (char c in "+-*/^()=,") {
				EndChar.Add (c);
			}
			foreach(char c in "0123456789."){
				NumChar.Add (c);
			}
			foreach (char c in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") {
				NameChar.Add (c);
			}
			OpTypeMap.Add ('+', OpType.Add);
			OpTypeMap.Add ('-', OpType.Sub);
			OpTypeMap.Add ('*', OpType.Mul);
			OpTypeMap.Add ('/', OpType.Div);
			OpTypeMap.Add ('^', OpType.Exp);
			OpTypeMap.Add ('(', OpType.Lbr);
			OpTypeMap.Add (')', OpType.Rbr);
			OpTypeMap.Add (',', OpType.Com);
			OpTypeMap.Add ('=', OpType.Equ);
		}


		private string _expr;

		public string Expr{
			get{ return _expr;}
			set{ _expr = value; isCompiled = false;}
		}

		private Token root;

		private bool isCompiled = false;

		private static OpType ParseOpType(char c){ 
			return OpTypeMap [c];
		}

		private List<Token> Parse(){

			var tokens = new List<Token> ();
			MachineStatus status = MachineStatus.Start;

			int scanStart = -1;
			for (int i = 0; i <= Expr.Length;) {
				char c = '=';
				if(i < Expr.Length) 
					c = Expr [i];
				switch (status) { 
				case MachineStatus.Start:
					if (NumChar.Contains (c)) {
						status = MachineStatus.Num;
						scanStart = i++; 
						continue;
					} else if (NameChar.Contains (c)) {
						status = MachineStatus.Name;
						scanStart = i++; 
						continue;
					} else if (EndChar.Contains (c)) {
						tokens.Add (new Token{ Op = ParseOpType (c), Value = "" + c });
						scanStart = i++; 
						continue;
					} else if (c == ' ' || c == '\t') {
						scanStart = i++;
						continue;
					}  else {
						i++;
					}
					break;
				case MachineStatus.Num:
					if (NumChar.Contains (c)) {
						i++;
					} else {
						status = MachineStatus.Start;
						tokens.Add (new Token{Op = OpType.Num, Value = Expr.Substring (scanStart, i-scanStart)});
					}
					break; 
				case MachineStatus.Name:
					if (NameChar.Contains (c) || NumChar.Contains (c)) { 
						i++;
					} else {
						//llk
						while (c == ' ' || c == '\t') {
							i++;
							c = i < Expr.Length ? Expr [i] : '=';
						}
						tokens.Add (new Token{Op = (c == '(' ? OpType.Fun : OpType.Var), Value = Expr.Substring (scanStart, i-scanStart)});
						status = MachineStatus.Start;
					}
					break;
				}
			}
			return tokens;
		}

		public Calculator(string expr){
			Expr = expr;
		}

		//算符优先级
		private static bool OperatorPrecedence(Token operatorLeft, Token operatorRight){
			var precedence = new Dictionary<OpType, Dictionary<OpType, bool>> {
				{OpType.Add, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, false}, {OpType.Div, false}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Sub, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, false}, {OpType.Div, false}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Mul, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Div, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Exp, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Lbr, new Dictionary<OpType, bool>{ {OpType.Add, false}, {OpType.Sub, false}, {OpType.Mul, false}, {OpType.Div, false}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, true}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Rbr, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, true}, {OpType.Lbr, true}, {OpType.Rbr, true}, {OpType.Fun, true}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Fun, new Dictionary<OpType, bool>{ {OpType.Add, false}, {OpType.Sub, false}, {OpType.Mul, false}, {OpType.Div, false}, {OpType.Exp, false}, {OpType.Lbr, false}, {OpType.Rbr, false}, {OpType.Fun, false}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Com, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, true}, {OpType.Lbr, true}, {OpType.Rbr, true}, {OpType.Fun, true}, {OpType.Com, true}, {OpType.Equ, true}}},
				{OpType.Equ, new Dictionary<OpType, bool>{ {OpType.Add, true}, {OpType.Sub, true}, {OpType.Mul, true}, {OpType.Div, true}, {OpType.Exp, true}, {OpType.Lbr, true}, {OpType.Rbr, true}, {OpType.Fun, true}, {OpType.Com, true}, {OpType.Equ, true}}},
			};
			return precedence[operatorLeft.Op][operatorRight.Op];
		}

		public void Compile(){
			if (isCompiled)
				return;

			var	operators = new Stack<Token> ();
			var	operands = new Stack<Token> ();
			var tokens = Parse ();
			foreach (var t in tokens) {
				var token = t;
				if (token.Op == OpType.Num || token.Op == OpType.Var) {
					operands.Push (token);
				} else {
					if (operators.Count > 0 && OperatorPrecedence (operators.Peek (), token)) {
						do {
							var expr = Reduce (operators, operands, token);
							if(expr != null) operands.Push(expr);
						} while(operators.Count > 0 && !token.Ignore && OperatorPrecedence (operators.Peek (), token));
					} else {
						if (token.Ignore || token.Op == OpType.Equ)
							break;
						operators.Push (token);
						continue;
					}
					if (token.Ignore || token.Op == OpType.Equ)
						continue;
					operators.Push (token);

				}
			} 
			if (operands.Count > 1 || operators.Count > 0) {
				throw new FormatException ("expr error:" + Expr);
			}
			root = operands.Pop ();
		}

		private Expr Reduce(Stack<Token> operators, Stack<Token> operands, Token token){
			switch (operators.Peek ().Op) {
			case OpType.Add:
			case OpType.Sub:
			case OpType.Mul:
			case OpType.Div:
			case OpType.Exp:
				var token2 = operands.Pop ();
				var token1 = operands.Pop ();
				return new Calc.Expr (operators.Pop ()).AppendOperands (token1 is Expr ? (token1 as Expr) : new Expr (token1), token2 is Expr? (token2 as Expr) : new Expr (token2));
			case OpType.Lbr:
				if (token.Op == OpType.Rbr) {
					operators.Pop ();
					if (operators.Count > 0 && operators.Peek ().Op == OpType.Fun) { 
						var expr = new Expr (operators.Peek ());
						while (operands.Count > 0) {
							token1 = operands.Peek ();
							if (token1.Index > expr.Index && token1.Index < token.Index) {
								expr.InsertOperands (token1 is Expr ? token1 as Expr : new Expr (token1));
								operands.Pop ();
							} else {
								break;
							}
						}
						operators.Pop ();
						token.Ignore = true;
						return expr;
					} else {
						var result = operands.Pop ();
						token.Ignore = true; 
						return result is Expr ? result as Expr : new Expr (result);
					}
				} else if (token.Op == OpType.Com) {
					token.Ignore = true;
					return null;
				}
				throw new FormatException ("parse expr error, miss match ( found");
			case OpType.Equ:
			case OpType.Com:
			case OpType.Rbr:
			case OpType.Fun:
				throw new FormatException ("parse expr error, miss match ) found");
			}
			return null;
		}

		public double Calculate(Dictionary<string, object> variables){
			if (!isCompiled)
				Compile ();

			return root.ValueOf (variables);
		}

		class Obj{
			public int aa{ get; set; }
			public float bb{ get; set; }
			public double cc{ get; set; }
			public string dd{ get; set; }
			public Obj ee{ get; set; }
		}
		public static int Main(string[] args)
		{
			//var c = new Calculator ("1.2334 + pi *1.333 + obj1.itemA.length * ((1+2) * (3+ab) ^ var)/func(a+1)");
			while (true) {
				string line = Console.ReadLine ();
				if (line.Equals ("exit"))
					break;
				var c = new Calculator (line);
				try{
					Console.WriteLine ("result of " + line + " is :" + c.Calculate (new Dictionary<string, object>(){
						{"x", 3},
						{"y", new Obj(){aa=19, bb=2.33f, cc=0.9, dd="232.11", ee= new Obj{aa=2, bb=3.14f, dd="2.1323"}}},
						{"pi", "3.14"},
					}));
				}catch(Exception ex){
					Console.WriteLine (ex.Message +  ex.StackTrace);
				}
			}
			return 0;
		}
	}
}
